#include <thread>
#include <iostream>
#include <vector>

/*
 *  运行时决定线程数量: std::thread::hardware_concurrency()
 *  实现了一个并行版的std::accumulate。代码中将整体工作拆分成小任务交给每个线程去做。
 */

template<typename Iterator,typename T>
// 类模板
struct accumulate_block
{
    void operator()(Iterator first,Iterator last,T& result)
    {
        result=std::accumulate(first,last,result);
    }
};

// 函数模板
template<typename Iterator,typename T>
T parallel_accumulate(Iterator first,Iterator last,T init)
{
    // std::distance：计算输入迭代器的范围内元素个数
    unsigned long const length = std::distance(first,last);

    // 如果输入的范围为空①，就会得到init的值
    if(!length) 
        return init;
    
    unsigned long const min_per_thread = 25;
    // 如果范围内多于一个元素时，都需要用范围内元素的总数量除以线程(块)中最小任务数，从而确定启动线程的最大数量
    unsigned long const max_threads = ( length+min_per_thread-1 ) / min_per_thread; // 2

    // std::thread::hardware_concurrency()在新版C++标准库中是一个很有用的函数。
    // 这个函数会返回一个程序中的最多能有的线程数量(非强制)。返回值可以是CPU核芯的数量,当系统信息无法获取时，函数也会返回0。
    unsigned long const hardware_threads = std::thread::hardware_concurrency();
    std::cout << hardware_threads << std::endl;
    // 得到实际的线程数,因为上下文频繁的切换会降低线程的性能，所以你肯定不想启动的线程数多于硬件支持的线程数量
    // 当std::thread::hardware_concurrency()返回0，可以选择一个合适的数作为你的选择；在本例中选择了 2
    unsigned long const num_threads = std::min( (hardware_threads != 0) ? hardware_threads : 2, max_threads);
    // 每个线程中处理的元素数量,是范围中元素的总量除以线程的个数得出的
    unsigned long const block_size = length / num_threads;
    // 现在，确定了线程个数，通过创建一个std::vector<T>容器存放中间结果，
    std::vector<T> results(num_threads);
    // 为线程创建一个std::vector<std::thread>容器。这里需要注意的是，
    // 启动的线程数必须比num_threads少1个，因为在启动之前已经有了一个线程(主线程)。
    // 注意，这里只是创建了大小为num_threads-1的vector,但是没有实际赋值
    std::vector<std::thread> threads(num_threads-1);
    // 
    Iterator block_start = first;

    for(unsigned long i=0; i < (num_threads-1); ++i)
    {
        Iterator block_end = block_start;
        // 使用简单的循环来启动线程：block_end迭代器指向当前块的末尾
        // std::advance 用于将输入的迭代器前进（或者后退）指定长度的距离
        std::advance(block_end, block_size);
        // 
        threads[i] = std::thread(accumulate_block<Iterator,T>(), block_start, block_end, std::ref(results[i]));
        block_start = block_end;  // #8
    }

    accumulate_block<Iterator,T>()(block_start,last,results[num_threads-1]); // 9

    std::for_each(threads.begin(),threads.end(),
        std::mem_fn(&std::thread::join));  // 10
    
    
    return std::accumulate(results.begin(),results.end(),init); // 11
}